/*
 * @lc app=leetcode.cn id=3 lang=cpp
 *
 * [3] 无重复字符的最长子串
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
//回退法
     bool isDup(char c,vector<int>& aph) {
        int flag = ++aph[int(c)];
        if(flag > 1) {
            return false;
        } else {
            return true;
        }
    }
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        if(n == 0) {
            return 0;
        }
        vector<int> aph(130);
        vector<int> dp(n);
        int result = 1;
        dp[0] = 1;
        aph[int(s[0])] = 1;
        for(int i = 1;i < n;i++) {
            if(isDup(s[i],aph)) {
                dp[i] = dp[i - 1] + 1;
                result = max(result, dp[i]);
            }else {
                //重置aph
                fill(aph.begin(),aph.end(),0);
                aph[int(s[i])] = 1;
                char flag = s[i];
                int j = i - 1;
                //回退找最大子串
                while(j > 0 && s[j] != s[j+1]) {
                    if(s[j] == flag) {
                        break;
                    }
                    aph[int(s[j])] = 1;
                    dp[i]++;
                    j--;
                }
                dp[i]++;
            }
        }
        return result;
    }
};
// @lc code=end

//移动窗口法
int lengthOfLongestSubstring(string s) {
        unordered_set<char> occ;
        int n = s.size(); 
        int right = -1, ans = 0;
        //滑动窗口
        for (int left = 0; left < n; left++) {
            if (left != 0) {
                occ.erase(s[left - 1]);
            }
            //如果该数是没有出现过的，右边就向右移动一位
            while (right + 1 < n && !occ.count(s[right + 1])) {
                occ.insert(s[right + 1]);
                right++;
            }
            //记录最大值
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
